////////////////////////////////////////////////////////////////////////////////////////////////////
/// Copyright (c) 2009 - 2010 RacoonStudios
///
/// Permission is hereby granted, free of charge, to any person obtaining a copy of this
/// software and associated documentation files (the "Software"), to deal in the Software
/// without restriction, including without limitation the rights to use, copy, modify, merge,
/// publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons
/// to whom the Software is furnished to do so, subject to the following conditions:
///
/// The above copyright notice and this permission notice shall be included in all copies or
/// substantial portions of the Software.
///
/// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
/// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
/// PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
/// FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
/// OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
/// DEALINGS IN THE SOFTWARE.
////////////////////////////////////////////////////////////////////////////////////////////////////

#pragma once
#ifndef quadtree_h__
#define quadtree_h__

#include "helper/fixedarray.h"
#include "helper/array.h"
#include "math/boundingbox.h"
#include "helper/list.h"

namespace Helper
{
	////////////////////////////////////////////////////////////////////////////////////////////////////
	/// \class	QuadTree
	///
	/// \brief	This is just a simple quad tree, as you might have expected. 
	///			This is just useful for 2 dimensional issues but if you want to
	///			get more information on that subject feel free and just search a bit.
	///
	/// \author	Markus
	/// \date	14.02.2010
	////////////////////////////////////////////////////////////////////////////////////////////////////
	template<class T>
	class QuadTree
	{
		public:

			class Node;

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	QuadTree()
			///
			/// \brief	Default constructor. 
			///
			/// \author	Markus
			/// \date	14.02.2010
			////////////////////////////////////////////////////////////////////////////////////////////////////
			QuadTree();

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	virtual ~QuadTree()
			///
			/// \brief	Finaliser. 
			///
			/// \author	Markus
			/// \date	14.02.2010
			////////////////////////////////////////////////////////////////////////////////////////////////////
			virtual ~QuadTree();




			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	void Initialize(const Math::boundingbox & bbox, uchar depth)
			///
			/// \brief	Initializes this object. 
			///
			/// \author	Markus
			/// \date	14.02.2010
			///
			/// \param	[in]	bbox	The bounding box. 
			/// \param	[in]	depth	The depth. 
			////////////////////////////////////////////////////////////////////////////////////////////////////
			void Initialize(const Math::boundingbox & bbox, uchar depth);




			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	const Math::boundingbox & GetBoundingBox() const
			///
			/// \brief	Gets the bounding box. 
			///
			/// \author	Markus
			/// \date	14.02.2010
			///
			/// \return	The bounding box. 
			////////////////////////////////////////////////////////////////////////////////////////////////////
			const Math::boundingbox & GetBoundingBox() const;

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	uchar GetDepth() const
			///
			/// \brief	Gets the depth. 
			///
			/// \author	Markus
			/// \date	14.02.2010
			///
			/// \return	The depth. 
			////////////////////////////////////////////////////////////////////////////////////////////////////
			uchar GetDepth() const;

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	int GetNumNodes(uchar level) const
			///
			/// \brief	Gets a number nodes. 
			///
			/// \author	Markus
			/// \date	14.02.2010
			///
			/// \param	[in]	level	The level. 
			///
			/// \return	The number nodes. 
			////////////////////////////////////////////////////////////////////////////////////////////////////
			int GetNumNodes(uchar level) const;

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	tIndex GetNodeIndex(uchar level, ushort col, ushort row) const
			///
			/// \brief	Gets a node index. 
			///
			/// \author	Markus
			/// \date	14.02.2010
			///
			/// \param	[in]	level	The level. 
			/// \param	[in]	col		The col. 
			/// \param	[in]	row		The row. 
			///
			/// \return	The node index. 
			////////////////////////////////////////////////////////////////////////////////////////////////////
			tIndex GetNodeIndex(uchar level, ushort col, ushort row) const;

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	tSize GetNumNodesInTree() const
			///
			/// \brief	Gets the number nodes in tree. 
			///
			/// \author	Markus
			/// \date	14.02.2010
			///
			/// \return	The number nodes in tree. 
			////////////////////////////////////////////////////////////////////////////////////////////////////
			tSize GetNumNodesInTree() const;

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	const Node & GetNodeByIndex(tIndex i) const
			///
			/// \brief	Gets a node by index. 
			///
			/// \author	Markus
			/// \date	14.02.2010
			///
			/// \param	[in]	i	The. 
			///
			/// \return	The node by index. 
			////////////////////////////////////////////////////////////////////////////////////////////////////
			const Node & GetNodeByIndex(tIndex i) const;

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	Node & NodeByIndex(tIndex i)
			///
			/// \brief	Node by index. 
			///
			/// \author	Markus
			/// \date	14.02.2010
			///
			/// \param	[in]	i	The. 
			///
			/// \return	. 
			////////////////////////////////////////////////////////////////////////////////////////////////////
			Node & NodeByIndex(tIndex i);

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	Node * FindContainmentNode(const Math::boundingbox & bbox)
			///
			/// \brief	Searches for the first containment node. 
			///
			/// \author	Markus
			/// \date	14.02.2010
			///
			/// \param	[in]	bbox	The bounding box. 
			///
			/// \return	null if it fails, else the found containment node. 
			////////////////////////////////////////////////////////////////////////////////////////////////////
			Node * FindContainmentNode(const Math::boundingbox & bbox);




			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \class	Node
			///
			/// \brief	Node. 
			///
			/// \author	Markus
			/// \date	14.02.2010
			////////////////////////////////////////////////////////////////////////////////////////////////////
			class Node
			{
				public:

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	Node()
					///
					/// \brief	Default constructor. 
					///
					/// \author	Markus
					/// \date	14.02.2010
					////////////////////////////////////////////////////////////////////////////////////////////////////
					Node();

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	~Node()
					///
					/// \brief	Finaliser. 
					///
					/// \author	Markus
					/// \date	14.02.2010
					////////////////////////////////////////////////////////////////////////////////////////////////////
					~Node();




					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	void Initialize(QuadTree<T> * tree, uchar level, ushort col, ushort row)
					///
					/// \brief	Initializes this object. 
					///
					/// \author	Markus
					/// \date	14.02.2010
					///
					/// \param	[in]	tree	If non-null, the tree. 
					/// \param	[in]	level	The level. 
					/// \param	[in]	col		The col. 
					/// \param	[in]	row		The row. 
					////////////////////////////////////////////////////////////////////////////////////////////////////
					void Initialize(QuadTree<T> * tree, uchar level, ushort col, ushort row);




					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	char GetLevel() const
					///
					/// \brief	Gets the level. 
					///
					/// \author	Markus
					/// \date	14.02.2010
					///
					/// \return	The level. 
					////////////////////////////////////////////////////////////////////////////////////////////////////
					char GetLevel() const;

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	ushort GetColumn() const
					///
					/// \brief	Gets the column. 
					///
					/// \author	Markus
					/// \date	14.02.2010
					///
					/// \return	The column. 
					////////////////////////////////////////////////////////////////////////////////////////////////////
					ushort GetColumn() const;

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	ushort GetRow() const
					///
					/// \brief	Gets the row. 
					///
					/// \author	Markus
					/// \date	14.02.2010
					///
					/// \return	The row. 
					////////////////////////////////////////////////////////////////////////////////////////////////////
					ushort GetRow() const;

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	Array<T> & GetElementArray()
					///
					/// \brief	Gets the element array. 
					///
					/// \author	Markus
					/// \date	14.02.2010
					///
					/// \return	The element array. 
					////////////////////////////////////////////////////////////////////////////////////////////////////
					Array<T> & GetElementArray();

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	const Math::boundingbox & GetBoundingBox() const
					///
					/// \brief	Gets the bounding box. 
					///
					/// \author	Markus
					/// \date	14.02.2010
					///
					/// \return	The bounding box. 
					////////////////////////////////////////////////////////////////////////////////////////////////////
					const Math::boundingbox & GetBoundingBox() const;

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	Node * FindContainmentNode(const Math::boundingbox & bbox)
					///
					/// \brief	Searches for the first containment node. 
					///
					/// \author	Markus
					/// \date	14.02.2010
					///
					/// \return	null if it fails, else the found containment node. 
					////////////////////////////////////////////////////////////////////////////////////////////////////
					Node * FindContainmentNode(const Math::boundingbox & bbox);

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	void SetElement(const T & element)
					///
					/// \brief	Sets the element. 
					///
					/// \author	Markus
					/// \date	14.02.2010
					///
					/// \param	[in]	element	The element. 
					////////////////////////////////////////////////////////////////////////////////////////////////////
					void SetElement(const T & element);

					////////////////////////////////////////////////////////////////////////////////////////////////////
					/// \fn	const T & GetElement() const
					///
					/// \brief	Gets the element. 
					///
					/// \author	Markus
					/// \date	14.02.2010
					///
					/// \return	The element. 
					////////////////////////////////////////////////////////////////////////////////////////////////////
					const T & GetElement() const;

				protected:

				private:

					friend class QuadTree;


					Node * m_children[4];

					char m_level;

					ushort m_col;
					ushort m_row;

					Math::boundingbox m_bbox;

					T m_element;

			};


		protected:

			friend class Node;


			tSize m_treeDepth;

			Math::boundingbox m_bbox;
			Math::vector3 m_baseNodeSize;

			FixedArray<Node> m_nodeArray;

		private:

	};





	///
	template<class T>
	QuadTree<T>::QuadTree():
	m_treeDepth(0),
		m_baseNodeSize(0.0f,0.0f,0.0f)
	{

	}


	///
	template<class T>
	QuadTree<T>::~QuadTree()
	{

	}





	///
	template<class T>
	void QuadTree<T>::Initialize(const Math::boundingbox &bbox, uchar depth)
	{
		this->m_treeDepth = depth;

		this->m_bbox = bbox;

		int base = 1 << (this->m_treeDepth - 1);

		this->m_baseNodeSize.set(this->m_bbox.getSize().getx() / base,
								 this->m_bbox.getSize().gety(),
								 this->m_bbox.getSize().getz() / base);

		tSize nodesCount = this->GetNumNodes(this->m_treeDepth);

		this->m_nodeArray.SetSize(nodesCount);

		this->m_nodeArray[0].Initialize(this, 0, 0, 0);
	}





	///
	template<class T>
	uchar QuadTree<T>::GetDepth() const
	{
		return this->m_treeDepth;
	}


	///
	template<class T>
	const Math::boundingbox & QuadTree<T>::GetBoundingBox() const
	{
		return this->m_bbox;
	}


	///
	template<class T>
	int QuadTree<T>::GetNumNodes(uchar level) const
	{
		return 0x55555555 & ((1 << level * 2) - 1);
	}


	///
	template<class T>
	tSize QuadTree<T>::GetNumNodesInTree() const
	{
		return this->m_nodeArray.Size();
	}


	///
	template<class T>
	tIndex QuadTree<T>::GetNodeIndex(uchar level, ushort col, ushort row) const
	{
		return this->GetNumNodes(level) + (row << level) + col;
	}


	///
	template<class T>
	typename QuadTree<T>::Node * QuadTree<T>::FindContainmentNode(const Math::boundingbox &bbox)
	{
		return this->m_nodeArray[0].FindContainmentNode(bbox);
	}





	///
	template<class T>
	QuadTree<T>::Node::Node():
	m_level(-1),
		m_col(0),
		m_row(0)
	{
		for(int i = 0; i < 4; i++)
			this->m_children[i] = 0;
	}


	///
	template<class T>
	QuadTree<T>::Node::~Node()
	{

	}




	///
	template<class T>
	void QuadTree<T>::Node::Initialize(Helper::QuadTree<T> *tree, uchar level, ushort col, ushort row)
	{
		this->m_level = level;
		this->m_col = col;
		this->m_row = row;

		float levelFactor = float(1 << (tree->m_treeDepth - 1 - this->m_level));

		static Math::vector3 center;
		static Math::vector3 extent;
		const Math::vector3 & baseSize = tree->m_baseNodeSize;
		const Math::boundingbox & treeBox = tree->m_bbox;
		Math::vector3 treeSize = treeBox.getSize();
		Math::vector3 treeCenter = treeBox.getCenter();

		center.set(treeCenter.getx() + (((this->m_col + 0.0f) * levelFactor * baseSize.getx()) - (treeSize.getx() * 0.5f)),
				   treeCenter.gety(),
				   treeCenter.getz() + (((this->m_row + 0.5f) * levelFactor * baseSize.getz()) - (treeSize.getz() * 0.5f)));

		extent.set(levelFactor * baseSize.getx() * 0.5f,
				   treeBox.getExtents().gety(),
				   levelFactor * baseSize.getz() * 0.5f);

		this->m_bbox.set(center, extent);

		uchar childLevel = this->m_level + 1;

		if(childLevel < tree->m_treeDepth)
		{
			for(ushort i = 0; i < 4; i++)
			{
				ushort childCol = 2 * this->m_col + (i & 1);
				ushort childRow = 2 * this->m_row + ((i & 2) >> 1);
				tIndex childIndex = tree->GetNodeIndex(childLevel, childCol, childRow);

				this->m_children[i] = &(tree->m_nodeArray[childIndex]);
				this->m_children[i]->Initialize(tree, childLevel, childCol, childRow);
			}
		}
	}




	///
	template<class T>
	const typename QuadTree<T>::Node & QuadTree<T>::GetNodeByIndex(tIndex index) const 
	{
		return this->m_nodeArray[index];
	}


	///
	template<class T>
	typename QuadTree<T>::Node & QuadTree<T>::NodeByIndex(tIndex index)
	{
		return this->m_nodeArray[index];
	}


	///
	template<class T>
	const Math::boundingbox & QuadTree<T>::Node::GetBoundingBox() const 
	{
		return this->m_bbox;
	}


	///
	template<class T>
	char QuadTree<T>::Node::GetLevel() const 
	{
		return this->m_level;
	}


	///
	template<class T>
	ushort QuadTree<T>::Node::GetColumn() const
	{
		return this->m_col;
	}


	///
	template<class T>
	ushort QuadTree<T>::Node::GetRow() const
	{
		return this->m_row;
	}


	///
	template<class T>
	void QuadTree<T>::Node::SetElement(const T &element)
	{
		this->m_element = element;
	}


	///
	template<class T>
	const T & QuadTree<T>::Node::GetElement() const
	{
		return this->m_element;
	}


	///
	template<class T>
	typename QuadTree<T>::Node * QuadTree<T>::Node::FindContainmentNode(const Math::boundingbox & bbox)
	{
		if(this->m_bbox.contains(bbox))
		{
			if(this->m_children[0] != 0)
			{
				for(int i = 0; i < 4; i++)
				{
					Node * containNode = this->m_children[i]->FindContainmentNode(bbox);

					if(containNode)
					{
						return containNode;
					}
				}
			}

			return this;
		}
		else
		{
			return NULL;
		}
	}

}

#endif // quadtree_h__